package com.ultrapower.charts.delaunay
{
	import flash.utils.ByteArray;
	
	
	
	
	/**
	 * Points in Euclidean space, implemented as double[].
	 *
	 * Includes simple geometric operations.
	 * Uses matrices; a matrix is represented as an array of Pnts.
	 * Uses simplices; a simplex is represented as an array of Pnts.
	 *
	 * @author Paul Chew
	 *
	 * Created July 2005.  Derived from an earlier, messier version.
	 *
	 * Modified Novemeber 2007.  Minor clean up.
	 * 
	 * Translated to AS3 version by lwz7512, in Sep 2008.
	 */
	public class Pnt
	{
		private var coordinates:Array;          // The point's coordinates
		
		public function Pnt(... coords)
		{			
			if(coords.length==1){
				coordinates = coords[0];
			}else{
				coordinates = coords;
			} 
			
		}
		
		private function deepCopyObject(value:Object):Object{
	  		var buffer:ByteArray = new ByteArray();
			buffer.writeObject(value);
			buffer.position = 0;
			var result:Object = buffer.readObject();
			return result;
	  	}
	  	
	    public function toString():String{
	    
	        if (coordinates.length == 0) return "Pnt()";
	        var result:String = "Pnt(" + coordinates[0];
	        for (var i:int = 1; i < coordinates.length; i++){
	        	result = result + "," + coordinates[i];
	        }	           
	        result = result + ")";
	        return result;
	    }
	
	    public function equals (other:Object):Boolean {
	        if (!(other is Pnt)) return false;
	        var p:Pnt = Pnt(other);
	        if (this.coordinates.length != p.coordinates.length){
	        	return false;
	        } 
	        for (var i:int = 0; i < this.coordinates.length; i++){
	        	if (this.coordinates[i] != p.coordinates[i]) {
	        		return false;
	        	}
	        }
	            
	        return true;
	    }
	
	    public function hashCode ():int {
	        var hash:int = 0;
	        for each (var c:Number in coordinates) {
	            var bits:int = getBits(c);
	            hash = (31*hash) ^ int(bits ^ (bits >> 32));
	        }
	        return hash;
	    }
	    
	    private function getBits(obj:Object):int{
	    	var byteArray:ByteArray = new ByteArray();
	    	byteArray.writeObject(obj);
	    	return byteArray.length;
	    }
	
	    /* Pnts as vectors */
	
	    /**
	     * @return the specified coordinate of this Pnt
	     * @throws ArrayIndexOutOfBoundsException for bad coordinate
	     */
	    public function coord (i:int):Number {
	        return this.coordinates[i];
	    }
	
	    /**
	     * @return this Pnt's dimension.
	     */
	    public function dimension ():int {
	        return coordinates.length;
	    }
	
	    /**
	     * Check that dimensions match.
	     * @param p the Pnt to check (against this Pnt)
	     * @return the dimension of the Pnts
	     * @throws IllegalArgumentException if dimension fail to match
	     */
	    public function dimCheck (p:Pnt):int {
	        var len:int = this.coordinates.length;
	        if (len != p.coordinates.length)
	            throw new Error("dimCheck Error, Dimension mismatch!");
	        return len;
	    }
	
	    /**
	     * Create a new Pnt by adding additional coordinates to this Pnt.
	     * @param coords the new coordinates (added on the right end)
	     * @return a new Pnt with the additional coordinates
	     */
	    public function extend (... coords):Pnt {
	        var result:Array = [];
	        result = deepCopyObject(coordinates) as Array;
	        for each(var item:Object in coords){
	        	result.push(item);
	        }	       
	        return new Pnt(result);
	    }
	
	    /**
	     * Dot product.
	     * @param p the other Pnt
	     * @return dot product of this Pnt and p
	     */
	    public function dot(p:Pnt):Number {
	        var len:int = dimCheck(p);
	        var sum:Number = 0;
	        for (var i:int = 0; i < len; i++)
	            sum += this.coordinates[i] * p.coordinates[i];
	        return sum;
	    }
	
	    /**
	     * Magnitude (as a vector).
	     * @return the Euclidean length of this vector
	     */
	    public function magnitude():Number {
	        return Math.sqrt(this.dot(this));
	    }
	
	    /**
	     * Subtract.
	     * @param p the other Pnt
	     * @return a new Pnt = this - p
	     */
	    public function subtract (p:Pnt):Pnt {
	        var len:int = dimCheck(p);
	        var coords:Array = [];
	        for (var i:int = 0; i < len; i++)
	            coords[i] = this.coordinates[i] - p.coordinates[i];
	        return new Pnt(coords);
	    }
	
	    /**
	     * Add.
	     * @param p the other Pnt
	     * @return a new Pnt = this + p
	     */
	    public function add (p:Pnt):Pnt {
	        var len:int = dimCheck(p);
	        var coords:Array = [];
	        for (var i:int = 0; i < len; i++)
	            coords[i] = this.coordinates[i] + p.coordinates[i];
	        return new Pnt(coords);
	    }
	
	    /**
	     * Angle (in radians) between two Pnts (treated as vectors).
	     * @param p the other Pnt
	     * @return the angle (in radians) between the two Pnts
	     */
	    public function angle (p:Pnt):Number {
	        return Math.acos(this.dot(p) / (this.magnitude() * p.magnitude()));
	    }
	
	    /**
	     * Perpendicular bisector of two Pnts.
	     * Works in any dimension.  The coefficients are returned as a Pnt of one
	     * higher dimension (e.g., (A,B,C,D) for an equation of the form
	     * Ax + By + Cz + D = 0).
	     * @param point the other point
	     * @return the coefficients of the perpendicular bisector
	     */
	    public function bisector (point:Pnt):Pnt {
	        dimCheck(point);
	        var diff:Pnt = this.subtract(point);
	        var sum:Pnt = this.add(point);
	        var dot:Number = diff.dot(sum);
	        return diff.extend(-dot / 2);
	    }
	
	    /* Pnts as matrices */
	
	    /**
	     * Create a String for a matrix.
	     * @param matrix the matrix (an array of Pnts)
	     * @return a String represenation of the matrix
	     */
	    public static function toString (matrix:Array):String {
	        var buf:String = "{";
	        for each(var row:Pnt in matrix){
	        	buf += (" " + row);
	        }
	        buf += " }";
	        return buf;
	    }
	
	    /**
	     * Compute the determinant of a matrix (array of Pnts).
	     * This is not an efficient implementation, but should be adequate
	     * for low dimension.
	     * @param matrix the matrix as an array of Pnts
	     * @return the determinnant of the input matrix
	     * @throws IllegalArgumentException if dimensions are wrong
	     */	    
	    public static function determinant (matrix:Array):Number {
	    	var result:Number;
	        if (matrix.length != Pnt(matrix[0]).dimension()){
	        	throw new Error("Matrix is not square");	
	        }	            
	        var columns:Array = new Array(matrix.length);
	        for (var i:int = 0; i < matrix.length; i++){
	        	columns[i] = true;
	        }
	        try {
	        	result =  determinantCols(matrix, 0, columns);
	        }catch (e:Error) {
	            throw new Error("Matrix is wrong shape");
	        }
	        return result;
	    }
	
	    /**
	     * Compute the determinant of a submatrix specified by starting row
	     * and by "active" columns.
	     * @param matrix the matrix as an array of Pnts
	     * @param row the starting row
	     * @param columns a boolean array indicating the "active" columns
	     * @return the determinant of the specified submatrix
	     * @throws ArrayIndexOutOfBoundsException if dimensions are wrong
	     */
	    private static function determinantCols(matrix:Array, row:int, columns:Array):Number{
	        if (row == matrix.length){
	        	return 1;
	        } 
	        var sum:Number = 0;
	        var sign:int = 1;
	        for (var col:int = 0; col < columns.length; col++) {
	            if (!columns[col]) continue;
	            columns[col] = false;
	            sum += sign * Pnt(matrix[row]).coordinates[col] * determinantCols(matrix, row+1, columns);
	            columns[col] = true;
	            sign = -sign;
	        }
	        return sum;
	    }
	
	    /**
	     * Compute generalized cross-product of the rows of a matrix.
	     * The result is a Pnt perpendicular (as a vector) to each row of
	     * the matrix.  This is not an efficient implementation, but should
	     * be adequate for low dimension.
	     * @param matrix the matrix of Pnts (one less row than the Pnt dimension)
	     * @return a Pnt perpendicular to each row Pnt
	     * @throws IllegalArgumentException if matrix is wrong shape
	     */
	    public static function cross(matrix:Array):Pnt {
	        var len:int = matrix.length + 1;
	        if (len != Pnt(matrix[0]).dimension()){
	        	throw new Error("Dimension mismatch");
	        }
	            
	        var columns:Array = new Array(len);
	        for (var i:int = 0; i < len; i++) columns[i] = true;
	        var result:Array = new Array(len);
	        var sign:int = 1;
	        try {
	            for (var j:int = 0; j < len; j++) {
	                columns[j] = false;
	                result[j] = sign * determinantCols(matrix, 0, columns);
	                columns[j] = true;
	                sign = -sign;
	            }
	        } catch (e:Error) {
	            throw new Error("Matrix is wrong shape");
	        }
	        return new Pnt(result);
	    }
	
	    /* Pnts as simplices */
	
	    /**
	     * Determine the signed content (i.e., area or volume, etc.) of a simplex.
	     * @param simplex the simplex (as an array of Pnts)
	     * @return the signed content of the simplex
	     */
	    public static function content (simplex:Array):Number {
	        var matrix:Array = new Array(simplex.length);
	        for (var i:int = 0; i < matrix.length; i++){
	        	matrix[i] = Pnt(simplex[i]).extend(1);
	        }
	            
	        var fact:int = 1;
	        for (var j:int = 1; j < matrix.length; j++) fact = fact*j;
	        var content:Number = determinant(matrix) / fact;
	        return content;
	    }
	
	    /**
	     * Relation between this Pnt and a simplex (represented as an array of
	     * Pnts). Result is an array of signs, one for each vertex of the simplex,
	     * indicating the relation between the vertex, the vertex's opposite facet,
	     * and this Pnt.
	     *
	     * <pre>
	     *   -1 means Pnt is on same side of facet
	     *    0 means Pnt is on the facet
	     *   +1 means Pnt is on opposite side of facet
	     * </pre>
	     *
	     * @param simplex an array of Pnts representing a simplex
	     * @return an array of signs showing relation between this Pnt and simplex
	     * @throws IllegalArgumentExcpetion if the simplex is degenerate
	     */
	    public function relation (simplex:Array):Array {
	        /* In 2D, we compute the cross of this matrix:
	         *    1   1   1   1
	         *    p0  a0  b0  c0
	         *    p1  a1  b1  c1
	         * where (a, b, c) is the simplex and p is this Pnt. The result is a
	         * vector in which the first coordinate is the signed area (all signed
	         * areas are off by the same constant factor) of the simplex and the
	         * remaining coordinates are the *negated* signed areas for the
	         * simplices in which p is substituted for each of the vertices.
	         * Analogous results occur in higher dimensions.
	         */
	        var dim:int = simplex.length - 1;
	        if (this.dimension() != dim)
	            throw new Error("Dimension mismatch");
	
	        /* Create and load the matrix */
	        var matrix:Array = new Array(dim+1);
	        /* First row */
	        var coords:Array = new Array(dim+2);
	        for (var m:int = 0; m < coords.length; m++) coords[m] = 1;
	        matrix[0] = new Pnt(coords);
	        /* Other rows */
	        for (var n:int = 0; n < dim; n++) {
	        	var tempCoords:Array = new Array(dim+2);	            
	            tempCoords[0] = this.coordinates[n];	            
	            for (var l:int = 0; l < simplex.length; l++){
	            	tempCoords[l+1] = Pnt(simplex[l]).coordinates[n];
	            }	               
	            matrix[n+1] = new Pnt(tempCoords);
	        }
	
	        /* Compute and analyze the vector of areas/volumes/contents */
	        var vector:Pnt = cross(matrix);
	        
	        var content:Number = vector.coordinates[0];
	        var result:Array = new Array(dim+1);
	        for (var i:int = 0; i < result.length; i++) {
	            var value:Number = vector.coordinates[i+1];	           
	            if (Math.abs(value) <= 1.0e-6 * Math.abs(content)){
	            	result[i] = 0;
	            }else if (value < 0){
	            	result[i] = -1;
	            }else {
	            	result[i] = 1;
	            }
	        }
	        if (content < 0) {
	            for (var j:int = 0; j < result.length; j++){
	            	 result[j] = -result[j];
	            }
	               
	        }
	        if (content == 0) {
	            for (var k:int = 0; k < result.length; k++){
	            	result[k] = Math.abs(result[k]);
	            }	                
	        }
	        return result;
	    }
	
	    /**
	     * Test if this Pnt is outside of simplex.
	     * @param simplex the simplex (an array of Pnts)
	     * @return simplex Pnt that "witnesses" outsideness (or null if not outside)
	     */
	    public function isOutside (simplex:Array):Pnt {
	    	
	        var result:Array = relation(simplex);
	        for (var i:int = 0; i < result.length; i++) {
	            if (result[i] > 0) return simplex[i];
	        }
	        return null;
	    }
	
	    /**
	     * Test if this Pnt is on a simplex.
	     * @param simplex the simplex (an array of Pnts)
	     * @return the simplex Pnt that "witnesses" on-ness (or null if not on)
	     */
	    public function isOn (simplex:Array):Pnt {
	        var result:Array = this.relation(simplex);
	        var witness:Pnt = null;
	        for (var i:int = 0; i < result.length; i++) {
	            if (result[i] == 0){
	            	witness = simplex[i];
	            } else if (result[i] > 0){
	            	return null;
	            } 
	        }
	        return witness;
	    }
	
	    /**
	     * Test if this Pnt is inside a simplex.
	     * @param simplex the simplex (an arary of Pnts)
	     * @return true iff this Pnt is inside simplex.
	     */
	    public function isInside (simplex:Array):Boolean {
	        var result:Array = this.relation(simplex);
	        for each(var r:int in result){
	        	 if (r >= 0) return false;
	        }
	        return true;
	    }
	
	    /**
	     * Test relation between this Pnt and circumcircle of a simplex.
	     * @param simplex the simplex (as an array of Pnts)
	     * @return -1, 0, or +1 for inside, on, or outside of circumcircle
	     */
	    public function vsCircumcircle (simplex:Array):int {
	        var matrix:Array = new Array(simplex.length + 1);
	        for (var i:int = 0; i < simplex.length; i++){
	        	matrix[i] = Pnt(simplex[i]).extend(1, Pnt(simplex[i]).dot(simplex[i]));	
	        }
	            
	        matrix[simplex.length] = this.extend(1, this.dot(this));
	        var d:Number = determinant(matrix);
	        var result:int = (d < 0)? -1 : ((d > 0)? +1 : 0);
	        var simplexContent:Number = content(simplex);
	        if (simplexContent < 0) result = - result;
	        return result;
	    }
	
	    /**
	     * Circumcenter of a simplex.
	     * @param simplex the simplex (as an array of Pnts)
	     * @return the circumcenter (a Pnt) of simplex
	     */
	    public static function circumcenter (simplex:Array):Pnt {
	        var dim:int = Pnt(simplex[0]).dimension();
	        if (simplex.length - 1 != dim){
	        	throw new Error("Dimension mismatch");
	        }
	            
	        var matrix:Array = [dim];
	        for (var i:int = 0; i < dim; i++){
	        	matrix[i] = Pnt(simplex[i]).bisector(simplex[i+1]);
	        }
	            
	        var hCenter:Pnt = cross(matrix);      // Center in homogeneous coordinates
	        var last:Number = hCenter.coordinates[dim];
	        var result:Array = [dim];
	        for (var j:int = 0; j < dim; j++){
	        	result[j] = hCenter.coordinates[j] / last;
	        } 
	        return new Pnt(result);
	    }
	
		public function get data():Array{
			return this.coordinates;
		}
	    

	}//end of class
}